package com.chj.jz.dp.class03;

public class Code09_LongestIncreasingSubsequence {
	/**
	 * @param nums:
	 *            An integer array
	 * @return: The length of LIS (longest increasing subsequence)
	 */
	public static int longestIncreasingSubsequence(int[] nums) {
		// write your code here

		int n = nums.length;
		if (n == 0) {
			return 0;
		}

		int[] f = new int[n];
		int i, j;
		int res = 0;

		for (j = 0; j < n; j++) {
			f[j] = 1;

			for (i = 0; i < j; i++) {
				if (nums[i] < nums[j]) {
					f[j] = Math.max(f[i] + 1, f[j]);
				}
			}

			res = Math.max(res, f[j]);
		}

		return res;
	}

	public static void main(String[] args) {
		{
			int[] arr = new int[] { 5, 4, 1, 2, 3 };
			System.out.println(longestIncreasingSubsequence(arr));
		}
		{
			int[] arr = new int[] { 4, 2, 4, 5, 3, 7 };
			System.out.println(longestIncreasingSubsequence(arr));
		}
		// {
		// int[] arr = new int[] { 1, 2, 3, 4, 5 };
		// System.out.println(maxProfitIII(arr));
		// }
		// {
		// int[] arr = new int[] { 5, 4, 3, 2, 1 };
		// System.out.println(maxProfitIII(arr));
		// }

	}

}
